home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / program / swagn_r.zip / POINTERS.SWG / 0002_LINKLIST.PAS.pas < prev    next >
Pascal/Delphi Source File  |  1993-05-28  |  8KB  |  240 lines
  1. {
  2. The following is the LinkList Unit written by Peter Davis in his wonderful
  3. but, unFortunately, short-lived newsletter # PNL002.ZIP.  I have used this
  4. Unit to Write tests of three or four of the Procedures but have stumped my toe
  5. on his DELETE_HERE Procedure, the last one in the Unit.  I will post my tests
  6. in the next message For any who may wish to see it:  Pete's Unit is unmodified.
  7.  I almost think there is some kind of error in DELETE_HERE but he was too
  8. thorough For that.  Can you, or someone seeing this show me how to use this
  9. Procedure?  It will help me both With Pointers and With Units.
  10.  
  11. Here is the Unit:
  12. }
  13.  
  14. Unit LinkList;
  15.  
  16. { This is the linked list Unit acCompanying The Pascal NewsLetter, Issue #2.
  17.   This Unit is copyrighted by Peter Davis.
  18.   It may be freely distributed in un-modified Form, or modified For use in
  19.   your own Programs. Programs using any modified or unmodified Form of this
  20. (107 min left), (H)elp, More?   Unit must include a run-time and source visible recognition of the author,
  21.   Peter Davis.
  22. }
  23.  
  24. { The DataType used is Integer, but may be changed to whatever data Type
  25.   that you want.
  26. }
  27.  
  28. Interface
  29.  
  30.  
  31. Type
  32.   DataType = Integer;    { Change this data-Type to whatever you want  }
  33.  
  34.   Data_Ptr = ^Data_Rec;  { Pointer to our data Records                 }
  35.  
  36.   Data_Rec = Record      { Our Data Record Format                      }
  37.     OurData  : DataType;
  38.     Next_Rec : Data_Ptr;
  39.   end;
  40.  
  41.  
  42. Procedure Init_List(Var Head : Data_Ptr);
  43. Procedure Insert_begin(Var Head : Data_Ptr; Data_Value : DataType);
  44. Procedure Insert_end(Var Head : Data_Ptr; Data_Value : DataType);
  45. Procedure Insert_In_order(Var Head : Data_Ptr; Data_Value : DataType);
  46. Function Pop_First(Var Head : Data_Ptr) : DataType;
  47. Function Pop_Last(Var Head : Data_Ptr) : DataType;
  48. Procedure Delete_Here(Var Head : Data_Ptr; Our_Rec : Data_Ptr);
  49.  
  50.  
  51.  
  52. Implementation
  53.  
  54. Procedure Init_List(Var Head : Data_Ptr);
  55.  
  56. begin
  57.   Head := nil;
  58. end;
  59.  
  60. Procedure Insert_begin(Var Head : Data_Ptr; Data_Value : DataType);
  61.  
  62. { This Procedure will insert a link and value into the
  63.   beginning of a linked list.                             }
  64.  
  65. Var
  66.   Temp : Data_Ptr;                { Temporary  Pointer.            }
  67.  
  68. begin
  69.   new(Temp);                      { Allocate our space in memory.  }
  70.   Temp^.Next_Rec := Head;         { Point to existing list.        }
  71.   Head:= Temp;                    { Move head to new data item.    }
  72.   Head^.OurData := Data_Value;    { Insert Data_Value.             }
  73. end;
  74.  
  75. Procedure Insert_end(Var Head : Data_Ptr; Data_Value : DataType);
  76.  
  77. { This Procedure will insert a link and value into the
  78.   end of the linked list.                                 }
  79.  
  80. Var
  81.   Temp1,             { This is where we're going to put new data }
  82.   Temp2 : Data_Ptr;  { This is to move through the list.         }
  83.  
  84. begin
  85.   new(Temp1);
  86.   Temp2 := Head;
  87.   if Head=nil then
  88.     begin
  89.       Head := Temp1;                  { if list is empty, insert first   }
  90.       Head^.OurData := Data_Value;    { and only Record. Add value and   }
  91.       Head^.Next_Rec := nil;          { then put nil in Next_Rec Pointer }
  92.     end
  93.   else
  94.     begin
  95.       { Go to the end of the list. Since Head is a Variable parameter,
  96.         we can't move it through the list without losing Pointer to the
  97.         beginning of the list. to fix this, we use a third Variable:
  98.         Temp2.
  99.       }
  100.       While Temp2^.Next_Rec <> nil do    { Find the end of the list. }
  101.         Temp2 := Temp2^.Next_Rec;
  102.  
  103.       Temp2^.Next_Rec := Temp1;          { Insert as last Record.    }
  104.       Temp1^.Next_Rec := nil;            { Put in nil to signify end }
  105.       Temp1^.OurData := Data_Value;      { and, insert the data      }
  106.     end;
  107. end;
  108.  
  109. Procedure Insert_In_order(Var Head : Data_Ptr; Data_Value : DataType);
  110.  
  111. { This Procedure will search through an ordered linked list, find
  112.   out where the data belongs, and insert it into the list.        }
  113.  
  114. Var
  115.   Current,              { Where we are in the list               }
  116.   Next     : Data_Ptr;  { This is what we insert our data into.  }
  117.  
  118. begin
  119.   New(Next);
  120.   Current := Head;      { Start at the top of the list.          }
  121.  
  122.   if Head = Nil then
  123.     begin
  124.       Head:= Next;
  125.       Head^.OurData := Data_Value;
  126.       Head^.Next_Rec := Nil;
  127.     end
  128.   else
  129.   { Check to see if it comes beFore the first item in the list   }
  130.   if Data_Value < Current^.OurData then
  131.     begin
  132.       Next^.Next_Rec := Head;      { Make the current first come after Next }
  133.       Head := Next;                { This is our new head of the list       }
  134.       Head^.OurData := Data_Value; { and insert our data value.             }
  135.     end
  136.   else
  137.     begin
  138.       { Here we need to go through the list, but always looking one step
  139.         ahead of where we are, so we can maintain the links. The method
  140.         we'll use here is: looking at Current^.Next_Rec^.OurData
  141.         A way to explain that in english is "what is the data pointed to
  142.         by Pointer Next_Rec, in the Record pointed to by Pointer
  143.         current." You may need to run that through your head a few times
  144.         beFore it clicks, but hearing it in English might make it a bit
  145.         easier For some people to understand.                            }
  146.  
  147.       While (Data_Value >= Current^.Next_Rec^.OurData) and
  148.             (Current^.Next_Rec <> nil) do
  149.         Current := Current^.Next_Rec;
  150.       Next^.OurData := Data_Value;
  151.       Next^.Next_Rec := Current^.Next_Rec;
  152.       Current^.Next_Rec := Next;
  153.     end;
  154. end;
  155.  
  156. Function Pop_First(Var Head : Data_Ptr) : DataType;
  157.  
  158. { Pops the first item off the list and returns the value to the caller. }
  159.  
  160. Var
  161.   Old_Head : Data_Ptr;
  162.  
  163. begin
  164.   if Head <> nil then   { Is list empty? }
  165.     begin
  166.       Old_Head := Head;
  167.       Pop_First := Head^.OurData;  { Nope, so Return the value }
  168.       Head := Head^.Next_Rec;      { and increment head.       }
  169.       Dispose(Old_Head);           { Get rid of the old head.  }
  170.     end
  171.   else
  172.     begin
  173.       Writeln('Error: Tried to pop an empty stack!');
  174.       halt(1);
  175.     end;
  176. end;
  177.  
  178.  
  179. Function Pop_Last(Var Head : Data_Ptr) : DataType;
  180.  
  181. { This Function pops the last item off the list and returns the
  182.   value of DataType to the caller.                              }
  183.  
  184. Var
  185.   Temp : Data_Ptr;
  186.  
  187. begin
  188.   Temp := Head;       { Start at the beginning of the list. }
  189.   if head = nil then  { Is the list empty? }
  190.     begin
  191.       Writeln('Error: Tried to pop an empty stack!');
  192.       halt(1);
  193.     end
  194.   else
  195.   if head^.Next_Rec = Nil then { if there is only one item in list, }
  196.     begin
  197.       Pop_Last := Head^.OurData;  { Return the value               }
  198.       Dispose(Head);              { Return the memory to the heap. }
  199.       Head := Nil;                { and make list empty.           }
  200.     end
  201.   else
  202.     begin
  203.       While Temp^.Next_Rec^.Next_Rec <> nil do  { otherwise, find the end }
  204.         Temp := Temp^.Next_rec;
  205.       Pop_Last := Temp^.Next_Rec^.OurData;  { Return the value          }
  206.       Dispose(Temp^.Next_Rec);              { Return the memory to heap }
  207.       Temp^.Next_Rec := nil;                { and make new end of list. }
  208.     end;
  209. end;
  210.  
  211.  
  212. Procedure Delete_Here(Var Head : Data_Ptr; Our_Rec : Data_Ptr);
  213.  
  214.  
  215. { Deletes the node Our_Rec from the list starting at Head. The Procedure
  216.   does check For an empty list, but it assumes that Our_Rec IS in the list.
  217. }
  218.  
  219. Var
  220.   Current : Data_Ptr;  { Used to move through the list. }
  221.  
  222. begin
  223.   Current := Head;
  224.   if Current = nil then   { Is the list empty? }
  225.     begin
  226.       Writeln('Error: Cant delete from an empty stack.');
  227.       halt(1);
  228.     end
  229.   else
  230.     begin   { Go through list Until we find the one to delete. }
  231.       While Current^.Next_Rec <> Our_Rec do
  232.         Current := Current^.Next_Rec;
  233.       Current ^.Next_Rec := Our_Rec^.Next_Rec; { Point around old link. }
  234.       Dispose(Our_Rec);                        { Get rid of the link..  }
  235.     end;
  236. end;
  237.  
  238.  
  239. end.
  240.